# -*- coding=utf-8-*-
"""
@File:memory_selection
@Author:Created by Han X.Y
@Date:on 2021/8/2 18:54 
"""
"""
基于二叉树实现查找过程
"""
class BinaryTree:
    def __init__(self,val):
        self.val=val
        self.right=None
        self.left=None


def insert(root,val):
    """
    向二叉树对象节点插值
    Args:
        root: 二叉树
        val: 值

    Returns:

    """
    if root is None:
        root=BinaryTree(val)
    else:
        if val<root.val:
            root.left=insert(root.left,val)#递归的插入元素
        elif val>root.val:
            root.right=insert(root.right,val)
    return root

def query(root,val):
    """
    基于二叉树查询val
    Args:
        root:
        val:

    Returns:

    """
    if root is None:
        return -1
    elif root.val==val:
        return 1
    elif root.val >val:
        return query(root.left,val)
    else:
        return query(root.right.val)


def findmin(root):
    """
    寻找二叉树的最小值
    二叉查找树中最左边的节点即为最小值，要查找最小值，只需要遍历左子树的节点，直到空为止
    Args:
        root:

    Returns:

    """
    if root.left:
        return findmin(root.left)
    else:
        return root

def delnum(root,val):
    """
    删除root对应的值
    Args:
        root:
        val:

    Returns:

    """
    if root is None:
        return None
    elif val<root.val:
        return delnum(root.left,val)
    elif val>root.val:
        return delnum(root.right,val)
    else:
        #删除时需要区分左右子树为空的情况
        if root.left and root.right:
            #找到后继节点
            tmp=findmin(root.right)
            root.val=tmp.val
            root.right=delnum(root.right,val)#实际删除的是这个后继节点
        else:
            if root.left is None:
                root=root.left
            elif root.right is None:
                root=root.right
    return root


if __name__=="__main__":
    root=BinaryTree(3)
    for i in [2,1,4]:
        root=insert(root,i)
    print(query(root,3))
    print(query(root,1))
    print(root)
    root=delnum(root,3)
    print(root)
    print(query(root,1))

